package 算法.LeetCode91.每日打卡题目;

import 算法.NiuKe.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: 谢君臣
 * @create: 2021-02-14 14:52
 * @founction: XXXX
 *
 *
 * 根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有
 *              a+(n+1)b+nc=2(a+b)
 *                  ⟹a=c+(n-1)(b+c)
 *                         ⟹a+(n+1)b+nc=2(a+b)
 *                              ⟹a=c+(n−1)(b+c)
 */
public class day11 {
    public static void main(String[] args) {

    }
    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        Set<ListNode> visited = new HashSet<>();
        while (p!=null){
            if (visited.contains(p))
                return p;
            else
                visited.add(p);
            p = p.next;
        }
        return null;
    }
    public ListNode detectCycle1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
